本日重點：說明 F、H、T 和 chain

FIPS 205 第 33 頁 [1] 是 key pair 的結構。

n 在本系列要用什麼，可以看 FIPS 205 第 43 頁的 Table 2，本系列要實作的演算法是 SLH-DSA-SHA2-128s，因此在本系列 n 都是 16。

FIPS 205 第 34 頁就是 key pair 的演算法

input 是 SK.seed、SK.prf、PK.seed

PK.seed shall be generated using an approved random bit generator
...
Both SK.seed and SK.prf shall be generated using an
approved random bit generator, ...

通過 approved random bit generator (RBG) 亂數產生器獲得 SK.seed、SK.prf、PK.seed，亂數產生器本身也是有規範的，我會在 Day 4 探討他們，現在我們就先隨便產生三個亂數給 SK.seed、SK.prf、PK.seed。

slh_keygen_internal 演算法只有三行，從 Table 2 能看到 𝑑 是 7，ℎ′ 是 9

ADRS ← toByte(0, 32)
ADRS.setLayerAddress(𝑑 − 1)
PK.root ← xmss_node(SK.seed, 0, ℎ′ , PK.seed, ADRS)

toByte 和 setLayerAddress 在 Day 2 已經寫完了, 所以只要寫完xmss_node，就完成了 slh_keygen_internal。

xmss_node 的演算法在 FIPS 205 第 23 頁 [1]，我們看到 xmss_node 是一個遞迴，在這 13 行裡，ADRS member function 就是純粹的對 ADRS 賦值，就不再重複。我們先把重點放在 H

Algorithm 9 xmss_node(SK.seed, 𝑖, 𝑧, PK.seed, ADRS)
Computes the root of a Merkle subtree of WOTS+ public keys.
Input: Secret seed SK.seed, target node index 𝑖, target node height 𝑧, public seed PK.seed, address ADRS.
Output: 𝑛-byte root 𝑛𝑜𝑑𝑒.
1: if 𝑧 = 0 then
2:    ADRS.setTypeAndClear(WOTS_HASH)
3:    ADRS.setKeyPairAddress(𝑖)
4:    𝑛𝑜𝑑𝑒 ← wots_pkGen(SK.seed, PK.seed, ADRS)
5: else
6:    𝑙𝑛𝑜𝑑𝑒 ← xmss_node(SK.seed, 2𝑖, 𝑧 − 1, PK.seed, ADRS)
7:    𝑟𝑛𝑜𝑑𝑒 ← xmss_node(SK.seed, 2𝑖 + 1, 𝑧 − 1, PK.seed, ADRS)
8:    ADRS.setTypeAndClear(TREE)
9:    ADRS.setTreeHeight(𝑧)
10:   ADRS.setTreeIndex(𝑖)
11:   𝑛𝑜𝑑𝑒 ← H(PK.seed, ADRS, 𝑙𝑛𝑜𝑑𝑒 ∥ 𝑟𝑛𝑜𝑑𝑒)
12: endif
13: return node

FIPS 205 [1] 沒有深入說明 F、H、T 的關係，但 SPHINCS+ 有，我們看 SPHINCS+ v.3.1 [2] 第 9、10、11 頁

簡單來說，Tℓ 是一個 tweakable hash functions，是一個雜湊映射，將 ℓ*n byte 映射到另一個 n byte，也就是雜湊值。

不管 ℓ 是什麼，Tℓ 都會映射到另一個 n byte。

舉例來說，如果 ℓ 是 1，就是把 1 * n byte 映射到另一個 n byte。如果 ℓ 是 2，就是把 2*n byte 映射到另一個 n byte；當 ℓ 是 1 的時候, 就是 Tℓ 的一個特例，此為 F。當 ℓ 是 2 的時候, 也是 Tℓ 的一個特例，此為 H。

Tℓ 是這樣做映射的，FIPS 205 第 46 頁

寫完 Tℓ，然後 ℓ 代入 1 就是 F，代入 2 就是 H。

Tℓ 有 3 個地方要注意，逐一來看看

1. Trunc
2. PK.seed
3. compressed address

Trunc 是一個截斷 byte string 的 function，只保留最左邊 n 個bytes。

PK.seed 就是公鑰的種子，除此之外，他還有一個作用，在 FIPS 205 第 7 頁有這一段

PK.seed, which is used to provide domain separation between different SLH-DSA key pairs

PK.seed 還能用來作為不一樣的 key pairs 的 domain separation，今天不對此做過多探討，等程式寫完，本系列的最後幾天我們可以留時間來採討 domain separation。

compressed address 是 ADRS 的壓縮版，FIPS 205 第 45 頁是他的結構

所以還有一個 function 要寫，ADRS to compressed address

compress_adrs(unsigned char c[22], const unsigned char adrs[32])

n 在 SLH-DSA-SHA2-128s 是 16，toByte(0, 64 - n) 就是一個有 48 個 bytes 的 array，每一個元素都是 0。

現在我們再來看 H

H(PK.seed, ADRS, 𝑀_2) =
Trunc𝑛(SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀_2))

就是將 PK.seed, 48 個 bytes, compressed address, M_2 合併後計算 SHA2，然後只保留最左邊 16 個bytes。

至此，我們已經說明了 F、H、T，我們看一下 chain 的演算法 (FIPS 205 的第 18 頁)

Algorithm 5 chain(𝑋, 𝑖, 𝑠, PK.seed, ADRS)
Chaining function used in WOTS+.
Input: Input string 𝑋, start index 𝑖, number of steps 𝑠, public seed PK.seed, address ADRS.
Output: Value of F iterated 𝑠 times on 𝑋.
1: 𝑡𝑚𝑝 ← 𝑋
2: for 𝑗 from 𝑖 to 𝑖 + 𝑠 − 1 do
3:    ADRS.setHashAddress(𝑗)
4:    𝑡𝑚𝑝 ← F(PK.seed, ADRS,𝑡𝑚𝑝)
5: end for
6: return 𝑡𝑚𝑝

setHashAddress 我們在 Day 2 已經完成，所以，F 完成後 chain 也差不多了

至此，我們已經說明了 F、H、T 和 chain，但我還沒有把程式寫出來，Day 4 就會開始實作 F、H、T、PRF 和 chain。

References

1. FIPS 205 Stateless Hash-Based Digital Signature Standard
2. SPHINCS+ – Submission to the 3rd round of the NIST post-quantum project. v3.1
3. The SPHINCS+ reference code, accompanying the submission to NIST's Post-Quantum Cryptography project